With the popularity and development of social software, more and more people join the social network, which produces a lot of valuable information, including sensitive private information. Different users have different private requirements and therefore require different levels of privacy protection. The level of user privacy leak in social network is affected by many factors, such as the structure of social network graph and the threat level of the user himself. Aiming at the personalized differential privacy preserving problem and user privacy leak level problem, a Personalized Differential Privacy based on Skyline (PDPS) algorithm was proposed to publish social network relational data. Firstly, user's attribute vector was built. Secondly, the user privacy leak level was calculated by Skyline computation method and the user dataset was segmented according to this level. Thirdly, with the sampling mechanism, the users with different privacy requirements were protected at different levels to realize personalized differential privacy and noise was added to the integreted data. Finally, the processed data were analyzed for security and availability and published. The experimental results demonstrate that compared with the traditional Personalized Differential Privacy (PDP) method on the real data set, PDPS algorithm has better privacy protection quality and data availability.